package com.frx.leetoffer.dp;

/**
 * @author ：frx
 * @date ：Created in 2019/10/31 21:58
 * @description： n个桶里放入m条鱼,每个桶能放0-10条，有多少种放法
 * @modified By：
 * @version: ToDO
 */
public class DpFish {

    public static void main(String[] args){
        System.out.println(solutionOne(20,20));
    }


    /**
     * 存储前i个桶存放j条鱼的方法数
     */
    static int [][] dp = new int[21][200];
    /**
     * @description n个桶放j条鱼的方法数
     * @param bucketN 桶数
     * @param fishN 鱼数
     * @return
     */
    public static int solutionOne(int bucketN,int fishN){

        if (bucketN <= 0 || fishN < 0){
            return 0;
        }
        // 1个桶放小于等于10条鱼只有1种放法
        if (bucketN == 1 && fishN <= 10){
            return 1;
        }

        // 如果子问题没有计算就计算,否则直接返回即可

        if (dp[bucketN][fishN] == 0){
            for (int i=0;i<=10;i++){
                dp[bucketN][fishN] += solutionOne(bucketN-1,fishN-i);
            }
        }

        return dp[bucketN][fishN];
    }

}
